public class Test3 {
    //leetcode N皇后
    //https://leetcode.cn/problems/n-queens-ii/description/
    int ret;
    boolean[] vis, vis1, vis2;
    public int totalNQueens(int n) {
        //vis记录同一列是否存在皇后
        vis = new boolean[n];
        //vis1记录正交线上是否存在皇后
        vis1 = new boolean[2 * n];
        //vis2记录反交线上是否存在皇后
        vis2 = new boolean[2 * n];
        backTracing(n,0);
        return ret;
    }

    private void backTracing(int n,int row) {
        if (row >= n) ret++;
        for (int i = 0; i < n; i++) {
            if (!vis[i] && !vis1[row-i+n] && !vis2[row+i]) {
                vis[i] = true;
                vis1[row-i+n] = true;
                vis2[row+i] = true;
                backTracing(n,row+1);
                vis[i] = false;
                vis1[row-i+n] = false;
                vis2[row+i] = false;
            }
        }
    }
}
